from collections import Iterable
from collections import Mapping
from functools import reduce
from itertools import islice
from itertools import zip_longest
import operator

from algorithm.comparison import compare_list
from algorithm.list import inplace_map
from number_theory.gcd import inv_mod
from polynomial.polynomial import Polynomial

__all__ = ["PolynomialZn"]



class _PolynomialZn(Polynomial):

    __slots__ = ("_coeff",)
    member_type = int
    zero = 0
    one = 1

    def __init__(self, other = None):
        klass = type(self)
        if not other:
            self._coeff = []
        elif type(other) == klass:
            self._coeff = other._coeff[:]
        elif isinstance(other, Polynomial):
            self._coeff = [int(x) % klass.mod for x in other._coeff]
            self.remove_leading_zeros()
        elif isinstance(other, Iterable):
            self._coeff = [int(x) % klass.mod for x in other]
            self.remove_leading_zeros()
        else:
            self._coeff = [int(other) % klass.mod]
            self.remove_leading_zeros()

    def init(self, iterable):
        klass = type(self)
        mod = klass.mod
        if isinstance(iterable, Mapping):
            for deg, coeff in iterable.items():
                self[deg] = coeff
        else:
            self._coeff = [int(x) % mod for x in iterable]
            self.remove_leading_zeros()

    def assign(self, mapping):
        for deg, coeff in mapping.items():
            self[deg] = coeff

    def __lt__(self, other):
        mod = type(self).mod
        half_mod = mod >> 1
        reduce_half = lambda x: x if x <= half_mod else x - mod
        l1 = len(self._coeff)
        l2 = len(other._coeff)
        if l1 < l2:
            return True
        elif l1 > l2:
            return False
        for x, y in zip(reversed(self._coeff), reversed(other._coeff)):
            comparison = compare_list(abs, lambda x: x)(
                    reduce_half(x), reduce_half(y))
            if comparison < 0:
                return True
            elif comparison > 0:
                return False
        return False

    def __str__(self, variable = 'x'):
        klass = type(self)
        mod = klass.mod
        half_mod = mod >> 1
        l = []
        for deg, coeff in filter(lambda x: x[1], enumerate(self._coeff)):
            if coeff > half_mod:
                coeff -= mod
            if deg == 0:
                l.append(str(coeff))
            elif deg == 1:
                if coeff == 1:
                    l.append(variable)
                else:
                    l.append("{0}*{1}".format(coeff, variable))
            elif coeff == 1:
                l.append("{0}^{1}".format(variable, deg))
            else:
                l.append("{0}*{1}^{2}".format(coeff, variable, deg))
        s = " + ".join(reversed(l)) if l else "0"
        return s.replace("-1*", "-").replace("+ -", "- ")

    def __repr__(self, variable = 'x'):
        mod = type(self).mod
        l = []
        for deg, coeff in enumerate(self._coeff):
            l.append("{0}*{1}^{2}".format(repr(coeff), variable, deg))
        if l:
            return " + ".join(reversed(l)) + " % " + str(mod)
        else:
            return "0 % " + str(mod)

    def __setitem__(self, deg, coeff):
        coeff = coeff % type(self).mod
        length = len(self._coeff)
        if deg >= length:
            if coeff:
                self._coeff += [0] * (deg - length)
                self._coeff.append(coeff)
        elif deg < length - 1 or coeff:
            self._coeff[deg] = coeff
        else:
            self._coeff[-1] = 0
            self.remove_leading_zeros()

    def monic(self):
        if self:
            inverse = inv_mod(self._coeff[-1], type(self).mod)
            return self * inverse
        else:
            return type(self)()

    def to_monic(self):
        if self and self._coeff[-1] != 1:
            self *= inv_mod(self._coeff[-1], type(self).mod)
        return self

    def interpole(self, value):
        mod = type(self).mod
        return reduce(lambda x, y: (x * value + y) % mod,
                reversed(self._coeff), 0)

    @classmethod
    def binary_op(klass, left, right, op):
        mod = klass.mod
        return klass(op(x, y) % mod for x, y in
                zip_longest(left._coeff, right._coeff, fillvalue = 0))

    def __iadd__(self, other):
        mod = type(self).mod
        l1 = len(self._coeff)
        l2 = len(other._coeff)
        if l1 < l2:
            for deg in range(l1):
                self._coeff[deg] = (
                        self._coeff[deg] + other._coeff[deg]) % mod
            self._coeff += islice(other._coeff, l1, None)
        else:
            for deg in range(l2):
                self._coeff[deg] = (
                        self._coeff[deg] + other._coeff[deg]) % mod
            if l1 == l2:
                self.remove_leading_zeros()
        return self

    def __neg__(self):
        mod = type(self).mod
        return type(self)(mod - x if x else 0 for x in self._coeff)

    def __isub__(self, other):
        mod = type(self).mod
        l1 = len(self._coeff)
        l2 = len(other._coeff)
        if l1 < l2:
            for deg in range(l1):
                self._coeff[deg] = (
                        self._coeff[deg] - other._coeff[deg]) % mod
            self._coeff += (mod - x if x else 0 for x in
                    islice(other._coeff, l1, None))
        else:
            for deg in range(l2):
                self._coeff[deg] = (
                        self._coeff[deg] - other._coeff[deg]) % mod
            if l1 == l2:
                self.remove_leading_zeros()
        return self

    def __mul__(self, other):
        klass = type(self)
        mod = klass.mod
        if isinstance(other, klass):
            result = klass()
            result._coeff = [0] * (len(self._coeff) + len(other._coeff) - 1)
            for i, x in enumerate(self._coeff):
                for j, y in enumerate(other._coeff):
                    result._coeff[i + j] += x * y % mod
            inplace_map(lambda x: operator.imod(x, mod), result._coeff)
            return result.remove_leading_zeros()
        elif other:
            return klass(x * other % mod for x in self._coeff)
        else:
            return klass()

    @classmethod
    def trunc_mul(klass, lhs, rhs, degree):
        mod = klass.mod
        result = klass()
        result._coeff = [0] * degree
        for i in range(min(len(lhs._coeff), degree)):
            for j in range(min(len(rhs._coeff), degree - i)):
                result._coeff[i + j] += lhs._coeff[i] * rhs._coeff[j] % mod
        inplace_map(lambda x: operator.imod(x, mod), result._coeff)
        return result

    def __rmul__(self, other):
        klass = type(self)
        mod = klass.mod
        other %= mod
        if other:
            return klass(x * other % mod for x in self._coeff)
        else:
            return klass()

    def __imul__(self, other):
        if isinstance(other, type(self)):
            self = self * other
        else:
            mod = type(self).mod
            other %= mod
            if not other:
                self = []
            elif other != 1:
                inplace_map(lambda x: x * other % mod, self._coeff)
                self.remove_leading_zeros()
        return self

    def square(self):
        klass = type(self)
        mod = klass.mod
        result = klass()
        result._coeff = [0] * (len(self._coeff) * 2 - 1)
        for i, x in enumerate(self._coeff):
            for j in range(i):
                result._coeff[i + j] += 2 * x * self._coeff[j] % mod
            result._coeff[i << 1] = x ** 2 % mod
        inplace_map(lambda x: operator.imod(x, mod), result._coeff)
        return result.remove_leading_zeros()

    def __divmod__(self, other):
        if not other:
            raise ZeroDivisionError
        klass = type(self)
        mod = klass.mod
        quotient = klass()
        remainder = klass(self)
        l2 = len(other._coeff)
        deg_diff = len(remainder._coeff) - l2
        if deg_diff >= 0:
            inverse = inv_mod(other._coeff[-1], mod)
            quotient._coeff = [0] * (deg_diff + 1)
            while deg_diff >= 0:
                q = remainder._coeff[-1] * inverse % mod
                quotient._coeff[deg_diff] = q
                for deg, coeff in enumerate(other._coeff, deg_diff):
                    remainder._coeff[deg] = (
                            remainder._coeff[deg] - q * coeff) % mod
                remainder.remove_leading_zeros()
                deg_diff = len(remainder._coeff) - l2
        return quotient, remainder

    def __truediv__(self, other):
        if not other:
            raise ZeroDivisionError
        klass = type(self)
        mod = klass.mod
        inverse = inv_mod(other, mod)
        return klass(x * inverse % mod for x in self._coeff)

    def __itruediv__(self, other):
        if not other:
            raise ZeroDivisionError
        mod = type(self).mod
        inverse = inv_mod(other, mod)
        if inverse != 1:
            inplace_map(lambda x: x * inverse % mod, self._coeff)
        return self

    def __mod__(self, other):
        if not other:
            raise ZeroDivisionError
        remainder = type(self)(self)
        remainder %= other
        return remainder

    def __imod__(self, other):
        if not other:
            raise ZeroDivisionError
        mod = type(self).mod
        l2 = len(other._coeff)
        deg_diff = len(self._coeff) - l2
        while deg_diff >= 0:
            q = self._coeff[-1] * inv_mod(other._coeff[-1], mod) % mod
            for deg, coeff in enumerate(other._coeff, deg_diff):
                self._coeff[deg] = (self._coeff[deg] - q * coeff) % mod
            self.remove_leading_zeros()
            deg_diff = len(self._coeff) - l2
        return self

    def __pow__(self, exp, mod = None):
        result = type(self)(1)
        if mod is None:
            while exp:
                if exp & 1:
                    result *= self
                self = self.square()
                exp >>= 1
        else:
            while exp:
                if exp & 1:
                    result = result * self % mod
                self = self.square() % mod
                exp >>= 1
        return result

    def deriv(self):
        klass = type(self)
        mod = klass.mod
        return klass(deg * self._coeff[deg] % mod
                for deg in range(1, len(self._coeff)))


PolynomialZn = lambda n: type(
        "PolynomialZ" + str(n), (_PolynomialZn,), {"mod": n})
